package com.ch8;

import java.util.Arrays;
import java.util.Random;

/**
 * 求连续的最大子向量
 * @author Linxiaozhi
 *
 */
public class MaxSum {
	public static void main(String[] args) {
		int[] arr = generateArray(20, 30);
		for (int i = 0; i < arr.length; i++) {
			System.out.printf("%3d ", i + 1);
		}
		System.out.println();
		for (int i = 0; i < arr.length; i++) {
			System.out.printf("%3d ", arr[i]);
		}
		System.out.println();
		fun1(arr);
		fun2(arr);
		fun3(arr);
		fun4(arr);
	}

	static int[] generateArray(int size, int range) {
		int[] arr = new int[size];
		Random rand = new Random(System.currentTimeMillis());
		int range0 = range >>> 1;
		for (int i = 0; i < size; i++) {
			arr[i] = rand.nextInt(range) - range0;
		}
		return arr;
	}

	static void fun1(int[] arr) {
		int size = arr.length;
		int[] sum = new int[size + 1];
		sum[0] = 0;
		for (int i = 1; i <= size; i++) {
			sum[i] = sum[i - 1] + arr[i - 1];
		}
		int max = Integer.MIN_VALUE;
		int low = 0;
		int high = 0;
		for (int i = 1; i <= size; i++) {
			for (int j = i; j <= size; j++) {
				int t = sum[j] - sum[i - 1];
				//max = t > max ? t : max;
				if (t >= max) {
					max = t;
					low = i;
					high = j;
				}
			}
		}
		System.out.println("low:" + low + ",high:" + high + ",max:" + max);
	}

	static void fun2(int[] arr) {
		int size = arr.length;
		int max = Integer.MIN_VALUE;
		int low = 0;
		int high = 0;
		for (int i = 0; i < size; i++) {
			int temp = 0;
			for (int j = i; j < size; j++) {
				temp += arr[j];
				if (temp >= max) {
					max = temp;
					low = i + 1;
					high = j + 1;
				}
			}
		}
		System.out.println("low:" + low + ",high:" + high + ",max:" + max);
	}

	/**
	 * 递归的算法
	 * @param arr
	 */
	static void fun3(int[] arr) {
		int max = funr(arr, 0, arr.length - 1);
		System.out.println("max:" + max);
	}

	static int funr(int[] arr, int low, int high) {
		if (low == high)
			return arr[low];
		int mid = (low + high) / 2;
		int leftMax = funr(arr, low, mid);
		int rightMax = funr(arr, mid + 1, high);
		int left = Integer.MIN_VALUE;
		int temp = 0;
		for (int i = mid; i >= low; i--) {
			temp += arr[i];
			if (temp >= left) {
				left = temp;
			}
		}
		int right = Integer.MIN_VALUE;
		temp = 0;
		for (int i = mid + 1; i <= high; i++) {
			temp += arr[i];
			if (temp >= right) {
				right = temp;
			}
		}
		temp = leftMax >= rightMax ? leftMax : rightMax;
		temp = temp >= (left + right) ? temp : (left + right);
		return temp;
	}

	/**
	 * 最好的方法
	 * @param arr
	 */
	static void fun4(int[] arr) {
		int size = arr.length;
		int maxEndinghere = -10000;//Integer.MIN_VALUE;
		int maxSofar = -10000;//Integer.MIN_VALUE;
		int low1 = 0;
		int high1 = 0;
		int low = 0;
		int high = 0;
		for (int i = 0; i < size; i++) {
			//maxEndinghere += arr[i];
			//maxEndinghere = (maxEndinghere + arr[i]) >= arr[i] ? (maxEndinghere + arr[i]) : arr[i];
			int temp = maxEndinghere + arr[i];
			if (arr[i] >= temp) {
				maxEndinghere = arr[i];
				low1 = i + 1;
				high1 = i + 1;
			} else {
				maxEndinghere = temp;
				high1 = i + 1;
			}

			if (maxEndinghere >= maxSofar) {
				maxSofar = maxEndinghere;
				low = low1;
				high = high1;
			}

			//maxSofar = maxEndinghere >= maxSofar ? maxEndinghere : maxSofar;
		}
		System.out.println("low:" + low + ",high:" + high + ",max:" + maxSofar);
	}

}
